剑指 Offer 66. 构建乘积数组
https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/description/?favorite=xb9nqhhg
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

 


int* constructArr(int* a, int aSize, int* returnSize)
{
    int leftmul=1;
    int rightmul=1;

    for(int i=aSize-1;i>=0;i--)
    {
        //计算左乘
        leftmul=1;
        for(int j=0;j<i;j++)
        {
            leftmul*=a[j];
        }
        int tmp=a[i];
        a[i]=leftmul*rightmul;

        rightmul*=tmp;
    }
    *returnSize=aSize;
    return a;


}


int* constructArr(int* a, int aSize, int* returnSize){
    if (a == NULL || aSize < 2) {
        *returnSize = 0;
        return a;
    }

    int *res = (int *)malloc(aSize * sizeof(int));
    if (res == NULL ) {
        *returnSize = 0;
        return res;
    }

    memset(res, 0, aSize * sizeof(int));
    *returnSize = aSize;
    res[0] = 1;

    /* 某元素左边元素的乘积 */
    for (int i = 1; i < aSize; ++i) {
        res[i] = res[i - 1] * a[i - 1];
    }

    int right = 1;
    for (int i = aSize - 2; i >= 0; --i) {
        right *= a[i + 1];   // 某元素右边元素的乘积
        res[i] *= right;     // 某元素两边元素乘积再相乘
    }    

    return res;
}